package leetcode_800;

/**
 *@author 周杨
 *SubarrayProductLessThanK_713 计算一个数组里有多少连续子数组能满足乘积和小于K
 *describe:用浮动窗口法 每次改变窗口的大小 满足题意 AC 57%
 *2018年10月11日 下午2:24:18
 */
public class SubarrayProductLessThanK_713 {
	public static void main(String[] args) {
		SubarrayProductLessThanK_713 test=new SubarrayProductLessThanK_713();
		System.out.println(test.numSubarrayProductLessThanK(new int[] {10, 5, 2, 6}, 100));
	}
	
	public int numSubarrayProductLessThanK(int[] nums, int k) {
        int dp=1;
        int res=0;
        int left=-1;//定义浮动框为i-left
        for(int i=0;i<nums.length;++i) {
        	dp*=nums[i];
        	if(dp<k) {
        		res+=i-left;
        	}
        	else {
        		while(dp>=k&&left<i) {//不能超过浮窗最右边界
        			dp/=nums[++left];
        		}
        		res+=i-left;
        	}
        }
        return res;
    }
}
